1. Field of the Invention
The present invention is related to networking systems and in particular, to maximizing bandwidth resources in a Multiprotocol Label Switching (MPLS) system.
2. Background
Internet is the widely accepted medium for the interchange of information. Government, business entities and other organizations routinely use the Internet to provide and receive information, and the number of users is increasing. To support such increased usage, networks and supporting devices have become larger and more complex. However, even with the proliferation of such devices and network complexity, an Internet service provider (ISP) must still provide reliable service that can withstand link or node failures while maintaining high transmission capacity. Additionally, the devices used in the network links and the intermediate devices such as switches and routers are expensive items and thus should be used to their maximal capacity. Traffic engineering is one solution that enables ISPs to maximize device capacities while providing network resiliency.
Traffic engineering (TE) is a term that refers to the ability to control traffic flow in a network (notwithstanding a path chosen by a routing protocol) with a goal of reducing congestion thereby getting the most use out of the available devices. For example, a network topology typically has multiple paths between two points. However, a routing protocol will usually select a single path between the two points regardless of the load on the links that form the path. This may cause certain paths to be congested while the other paths are under-utilized. Traffic engineering facilitates load balancing or load sharing among the paths thereby enabling the network to carry more traffic between two points.
Multiprotocol Label Switching (MPLS) is a technology that, among others, allows traffic engineering to be performed. The principle behind MPLS, as its name implies, is using labels to switch packets along a path. This is in contrast to a routing lookup table in which the longest lookup on an Internet Protocol (IP) header is performed. A label distributing mechanism based on a Label Distribution Protocol (LDP) or existing protocols such as Resource Reservation Protocol (RSVP), which has been enhanced, allows for the assignment and distribution of the labels. RSVP is a protocol for reserving network resources to provide Quality of Service guarantees to application flows. Various control modules are responsible for facilitating and maintaining traffic engineering as well as for maintaining other relevant control information.
Referring to FIG. 1, an exemplary MPLS based router 100, among others, may include:
a routing module 110 that constructs a routing table 112 using conventional routing protocols, preferably a linked-state Interior Gateway Protocol (IGP) such as Intermediate System to Intermediate System (IS-IS), Open Shortest Path First (OSPF) and so forth;
a traffic engineering (TE) module 120 that enables explicitly specified label switched paths (LSPs) to be configured throughout a network using a TE topology database and a TE path calculation module, as will be described, which preferably in conjunction with RSVP and a label allocation module (not shown), assigns labels 122 to routes and supplements the above routing table with those labels to be further described with respect to FIG. 2;
a TE path calculation module 130 that calculates the xe2x80x9cbestxe2x80x9d path for the LSPs based on resources required by the path and the available resources in the network;
a TE topology database 140 that receives and stores information on link states of the network and available resources via the IGP assuming that it is a linked state IGP,
a TE link management module 150 that keeps track of and maintains all LSPs that have been set up; and
supporting protocols such as RSVP 160 and an IGP 170 with extensions for global flooding of resource information.
Explicitly routed LSPs are referred to as TE tunnels. FIG. 2 illustrates the operation of an MPLS system supporting unicast TE tunnel routing. Using an IGP and RSVP, each router on a path of a TE tunnel builds a routing table supplemented with labels. For this configuration, each router has its resource information flooded to the appropriate IGP link state database and accepts RSVP signaling requests. Generally, when a TE tunnel is being established, assuming it to be a dynamic path, the TE module sets the resource requirement of the path based on operator input or default. The TE path calculation module calculates a constrained short path from the xe2x80x9chead-endxe2x80x9d router to the xe2x80x9ctail-endxe2x80x9d router based on resources required to setup the path, which in this instance is path 200. RSVP then signals the routers along the path 200 that a setup is being performed. During setup, the routers on the path need to agree on the labels to be used for the packets traveling along the path. This label allocation procedure may also be performed by RSVP in that its signaling and the resource reservation features may be used to construct the TE tunnels. RSVP also requests labels from the label allocation module; these labels required for constructing the TE tunnel.
The TE module using RSVP causes router R1 at the head-end of the tunnel to send a setup request to the router Rn at the tail-end of the tunnel. The setup request travels along the calculated path 200 until it reaches the tail-end router Rn. Upon receipt of the setup request, the router Rn returns a setup reply to router R1 over the path 200 traveled by the setup request. When router Rn-1 receives the setup reply, it requests a label from the label allocation module, which allocates a label LRn-1 for the segment of the path. Router Rn-1 then establishes a mapping in its routing table between the label LRn-1 and the path to router Rn. Router Rn-1 then attaches the label LRn-1 to the setup reply and sends it xe2x80x9cupstreamxe2x80x9d to the previous xe2x80x9chopxe2x80x9d router Rn-2 on the path. In response to receiving the setup reply, Router Rn-2 requests and receives a label LRn-2, which it uses to allocate for that segment of the path and establishes a mapping in its routing table between the label LRn-2 and the path to router Rn-1. Router Rn-2 then replaces the label LRn-1 on the setup reply with its label LRn-2 and sends it to the next router Rn-3 on the path. Likewise, Router Rn-3, upon receiving the setup reply, requests and allocates a label LRn-3 for the segment of the path and establishes a mapping between the label LRn-3 and the path to router Rn-2. Router Rn-3 then replaces the label on the setup reply with its own label and sends the setup reply further upstream. This process is repeated for each router along the path 200 until the head-end router R1 receives the setup reply. In this instance, the setup reply will have a label LR2 attached thereto by the router R2 on the path. Router R1 then adds an entry to its routing table using the label LR2 which functions as an initial label for entering the TE tunnel created for the path.
Once the TE tunnel has been established, the TE module notifys the IGP as to the IP address of the TE tunnel. Once notified, the IGP can route packets through the TE tunnel using the IP address. In instances where the IGP is load balancing between a TE tunnel and a regular path, IGP may use a xe2x80x9cflowxe2x80x9d method or a xe2x80x9cround-robinxe2x80x9d method to load balance between the two paths. The flow method is really a load sharing method and may be performed in a following manner: a portion of a source address and a destination address of a packet may be combined and hashed to generate one of a pseudo-random range of numbers. The value of the number determines which path the packet is to follow. Assuming the packet is routed to the TE tunnel, the packet transmission mechanism through the tunnel is based on label switching.
For example, when router R1 receives a packet, it performs a conventional longest match lookup on the IP header. If the lookup indicates a label, router R1 recognizes that the packet is to be transmitted through the TE tunnel and affixes the initial label on the packet. After the packet is labeled, subsequent routers in the tunnel transmit the packet using only labels, that is, each router switches the label of an incoming packet with its label prior to sending the packet. The incoming label received by a router is used as an index to the routing table for the xe2x80x9cnext hopxe2x80x9d information. Note that the label switching mechanism operates similar to that of a layer two switching mechanism. In this manner, other than the head-end router, no longest match lookup is performed by subsequent routers.
FIG. 3 gives an example of how the MPLS TE system may be used to solve traffic congestion while maximizing resources. As shown, there are two paths from router C to router E. Typically, router C selects the shortest path to router E resulting in all traffic being channeled through router D. Thus, the resulting traffic volume creates congestion in that path while the path though router F and router G remains underloaded. To maximize performance of the overall network, it is desirable to shift some of the traffic from the congested path to the under-loaded path. One previous attempt to address the problem sets the cost of the path of the routers C-D-E equal to the cost of the path of the routers C-F-G-E. While such a method may be feasible in a simple network, it is cumbersome if not impossible in a network of complex topology. By using explicitly routed paths, MPLS traffic engineering is a more straightforward and flexible way of addressing this problem. For example, the traffic engineering module can establish a label-switched path from routers A-C-D-E and another label-switched path from routers B-C-F-G-E. By defining policies that determine which packets are to follow these paths, traffic flow across a network, even one of complex topology, can be managed.
xe2x80x9cConstraint-based routingxe2x80x9d is a technique that allows minimal operator intervention in setting up the TE tunnels. Constrained-based routing may be supported by the TE module and the TE path calculation module as described above. Prior to constraint-based routing, the operator configured the TE tunnels by specifying a sequence of hops that the path should follow. However, a problem concerning this form of traffic engineering is that considerable network configuration and re-configuration is required. Under constraint-based routing, an operator merely specifies the amount of traffic that is expected to flow in the TE tunnel. The MPLS TE system then calculates the paths based on constraints suitable for carrying the load and establishes explicit paths. These paths are established by considering resource requirements and resource availability, instead of simply using the shortest path. Examples of constraint factors considered by the MPLS TE system are bandwidth requirements, media requirements, a priority versus other flows and so forth.
Below is a table that lists a set of commands that may be used to configure an MPLS TE tunnel based on constraint-based routing.
One particular aspect of configuring an MPLS TE tunnel is that the bandwidth of the tunnel needs to be specified as shown in the following exemplary commands:
configure terminal
interface tunnel 1
tunnel destination 17. 17. 17. 17
tunnel mode mpls traffic-eng
tunnel mpls traffic-eng autoroute announce
tunnel mpls traffic-eng bandwidth 100
tunnel mpls traffic-eng priority 11
tunnel mpls traffic-eng path-option 1 dynamic
Stated differently, the operator specifies the amount of bandwidth a TE tunnel requires prior to enabling the tunnel, as this is a factor in constraint-based routing. However, where the traffic flow constantly changes within the tunnel, such bandwidth constraints may not necessarily result in efficient usage of the routers, an example which is shown below.
FIG. 4 shows various routers connected together by MPLS TE tunnels. Once the operator has configured the TE tunnels, the TE module along with the link management module, establish and maintain the tunnels. Tunnel paths are calculated at the tunnel head based on the required resources and the available resources, such as bandwidth. Router C is an example in which several TE tunnels enter and exit the router. By carefully monitoring the traffic flow, the operator may finely balance the allocation of bandwidth to the TE tunnels in view of the available bandwidth of the router. If the operator configures the tunnels based on peak traffic flow, it is possible that the aggregate peak traffic flow of the tunnels may be greater than the bandwidth of the router. This forces the operator to configure one or more TE tunnels elsewhere to share the traffic load. In certain instances, more routers may be needed to provide the load share. In many instances, however, it is quite possible that the peak traffic in the tunnels occurs at different time intervals and the router C has sufficient bandwidth to handle the traffic flow between the plurality of TE tunnels. In a network of complex topology where traffic patterns are constantly changing, it is generally difficult for the operator to predict the traffic flow and adjust the bandwidth of the individual tunnels accordingly. Further, because of the numerous routers involved, it is generally burdensome for the operator to continuously monitor traffic patterns and update the various bandwidth constraints.
The invention comprises an improved Multiprotocol Label Switching (MPLS) system within a network device for traffic engineering that determines an actual traffic flow within a traffic engineering (TE) tunnel and dynamically adjusts the bandwidth to reflect the actual traffic flow. The actual traffic flow may be ascertained by accessing an average byte counter in the physical link management module that keeps track of bytes flowing through the TE tunnel. The TE tunnel configuration information is usually stored at the head-end network device of the tunnel. According to one example, the improved MPLS system signals a path from the head-end network device to the tail-end network device using the adjusted bandwidth as one of the constraints for establishing the path. If the new path is different from the previous path then the previous path is xe2x80x9ctorn downxe2x80x9d and replaced by the new path as the TE tunnel.
As an example, the MPLS system, among others, comprises a TE module, a routing module, a TE path calculation module, a TE topology database and a TE link management module. The TE module is responsible for initiating a tunnel setup once the tail-end router and the bandwidth have been selected (assuming the current MPLS system is at the head router) under xe2x80x9cconstraint-basedxe2x80x9d routing. Using the TE topology database and the TE path calculation module, a constrained path calculation is performed to determine a path for the tunnel. Once tunnels are set up in the router, the TE link management module keeps track of the status of the tunnels such as whether a tunnel is being maintained or is being xe2x80x9ctorn downxe2x80x9d. The TE module supplements the routing table built by the routing module with labels to be used for label switching in a particular tunnel. The link management module keeps track of all tunnels through the router including the resources used such as allocated bandwidth and available bandwidth. In addition, there is a configuration table, which is stored in a memory and contains tunnel configurations specified by the operator or specified by default. Configuration information may include bandwidth requirements, media requirements, a priority verses other flows and so forth. The router may also have a physical link management module to allocate available resources in accordance with the configuration table. The physical link management module includes byte counters for each TE tunnel set up to monitor the traffic flow through the tunnel.
The improved MPLS system uses the byte counters to determine the actual traffic flow through the configured TE tunnels and dynamically re-configures the required bandwidth to reflect the traffic flow. This may be performed as a sub-module within the TE link management module or as a separate xe2x80x9cautobandwidthxe2x80x9d module. The autoband-width module has a global timer, which is global to the networking device. The global timer may be accessed by a supplemental MPLS command xe2x80x9cauto-bw timerxe2x80x9d, which at predetermined intervals set by the operator or by default, causes the global timer to take the average byte count for each tunnel for that interval and may store each average count in a register. Another supplemental MPLS command xe2x80x9cauto-bwxe2x80x9d determines the frequency at which the byte count for a particular tunnel is to be sampled to determine if a bandwidth adjustment is required. Each enabled xe2x80x9cauto-bwxe2x80x9d command is specific to an established TE tunnel. If a tunnel requires a bandwidth adjustment, the auto-bw command causes the autobandwidth module to update the bandwidth. This may be in the form of the autobandwidth module notifying the TE module that the bandwidth needs to be changed and the TE module changing the configuration table and performing a setup procedure. Alternatively, the autobandwidth module may change the configuration table and notify the TE module of the change causing the TE module, in turn, to perform the setup procedure. The features described above allow for bandwidth resources of a network to be efficiently utilized thereby maximizing its capacity while minimizing operator intervention. Further details and advantages will be apparent in the detailed description to follow.